package leetcode.hot100;

@SuppressWarnings("all")
public class _283_移动零_双指针 {

    // 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
    // 输入: [0,1,0,3,12]
    // 输出: [1,3,12,0,0]
    // 必须在原数组上操作，不能拷贝额外的数组
    // 尽量减少操作次数

    int[] nums;

    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        this.nums = nums;
        int len = nums.length;
        // 由于非零元素的相对位置不能改变，所以只能依次移动零，不能通过直接将零移动到末尾并缩小数组范围的方式完成
        // 可以参考冒泡排序的思想，但如果使用冒泡排序不能通过一次遍历来完成

        // 左指针左边均为非零数
        // 右指针左边直到左指针处均为零
        int left = 0;
        int right = 0;
        while (right < len) {
            if (nums[right] != 0) {
                swap(left++, right);
            }
            right++;
        }
    }

    private void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
